package leetcode.sword;

import java.util.HashMap;

public class Solution35 {

    public static void main(String[] args) {
        Node node0 = new Node(7);
        Node node1 = new Node(13);
        Node node2 = new Node(11);
        Node node3 = new Node(10);
        Node node4 = new Node(1);
        node0.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node1.random = node0;
        node2.random = node4;
        node3.random = node2;
        node4.random = node0;

        Solution35 s = new Solution35();
        Node newNode = s.copyRandomList(node0);

    }

    HashMap<Node, Node> oldToNew = new HashMap<>(); //记录从老节点到对应新节点的映射
    public Node copyRandomList(Node head) {
        Node newImgHead = new Node(0); //为了方便构建链表给新链表加一个虚头
        Node pre = newImgHead; // 记录前一个结点，方便添加next
        while(head!=null){
            //复制新节点
            Node newNode = new Node(head.val);
            pre.next = newNode;
            pre = newNode;
            //让新节点的random暂时指向它复制的旧节点
            //让旧节点映射到它复制出的新节点
            newNode.random = head;
            oldToNew.put(head, newNode);
            //旧节点向后一步
            head = head.next;
        }
        //遍历新链表，添加random，先用random找到对应的旧节点
        //再用旧节点的random找到应该跳转的旧节点，如果为空，停止
        //否则借助hashmap找到对应的新节点
        head = newImgHead.next; //从新链表的真正头开始
        while(head!=null){
            Node old = head.random.random;
            if(old==null){
                head.random = null;
            }else{
                head.random = oldToNew.get(old);
            }
            head = head.next;
        }
        return newImgHead.next;
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}